public class test {
    //leetcode 1745.分割回文串Ⅳ
    class Solution {
        public boolean checkPartitioning(String s) {
            // 1. 创建dp[]表
            int n = s.length();
            char[] nums = s.toCharArray();
            boolean[][] dp = new boolean[n][n];
            // 2. 初始化

            // 3. 填表
            for (int i = n - 1; i >= 0; i--) {
                for (int j = i; j < n; j++) {
                    if (nums[i] == nums[j]) {
                        dp[i][j] = (i + 1 < j) ? dp[i + 1][j - 1] : true;
                    }
                }
            }
            for(int i = 1;i < n;i++){
                for(int j = i;j < n - 1;j++){
                    if(dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1]){
                        return true;
                    }
                }
            }
            // 4. 返回值
            return false;
        }
    }
    //leetcode 873.最长的斐波那契子序列的长度
    class Solution {
        // 解法1. 一维dp(暴力 + 回溯)
        public int lenLongestFibSubseq1(int[] arr) {
            // 1. 创建dp表
            // key 代表结尾元素的值
            // value 代表该元素的下标
            TreeMap<Integer, Integer> map = new TreeMap<>();
            // dp[i]代表以该元素结尾时,最长斐波那契子序列的长度
            int n = arr.length;
            int[] dp = new int[n];
            if (n < 3) {
                return 0;
            }
            // 2. 初始化
            int max = 0;
            for (int i = 0; i < n; i++) {
                map.put(arr[i], i);
            }
            dp[2] = arr[0] + arr[1] == arr[2] ? 3 : 0;
            // 3. 填表
            for (int i = 3; i < n; i++) {
                for (int j = i - 1; j >= 1 && arr[j] * 2 > arr[i]; j--) {
                    // 找到一个 cnt 使得 cnt + arr[j] = arr[i]
                    int cnt = arr[i] - arr[j];
                    int right = j;
                    int left = map.getOrDefault(cnt, -1);
                    // 检查以arr[j]为arr[i]的前一个斐波那契序列数的情况下
                    // 能够找到最长的斐波那契子序列
                    while (left >= 0) {
                        // 若此次找到了,则接着上次查找的结果增长斐波那契子序列长度
                        dp[i] = Math.max(dp[i] >= 3 ? dp[i] + 1 : 3, dp[i]);
                        // 沿着上次最小的数继续往前查询
                        int tmp = left;
                        cnt = arr[right] - arr[left];
                        // 如果目标值cnt在arr[left]右边也是不行的
                        if (cnt >= arr[left])
                            break;
                        left = map.getOrDefault(cnt, -1);
                        right = tmp;
                    }
                    max = Math.max(max, dp[i]);
                    dp[i] = 0;
                }
            }
            // 4. 返回值
            return max;
        }

        // 解法2. 二维dp
        public int lenLongestFibSubseq(int[] arr) {
            // 1. 创建dp表
            int n = arr.length;
            //存储元素值以及元素下标
            HashMap<Integer,Integer> map = new HashMap<>();
            //代表以i和j作为结尾元素时的最长斐波那契子序列长度
            int[][] dp = new int[n][n];
            int max = 0;
            // 2. 初始化
            for(int i = 0;i < n;i++){
                map.put(arr[i],i);
            }
            dp[0][0] = 2;
            // 3. 填表
            for(int i = 0;i < n ;i++){
                for(int j = i - 1;j >= 0 && arr[j] * 2 > arr[i];j--){
                    int index = map.getOrDefault(arr[i] - arr[j],-1);
                    if(index >= 0){
                        dp[j][i] = Math.max(dp[index][j] + 1,3);
                    }
                    max = Math.max(dp[j][i],max);
                }
            }
            // 4. 返回值
            return max;
        }
    }
}
